package 左哥算法.ch17技巧篇.预处理;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 预处理数组：
 * 找代码中查询频繁的部分。尝试将查询的内容生成一个结构。
 * 之后的查询从这个结构中拿数据。
 */
public class Ch01 {
    /**
     * ch01：给你一个由G和R组成的字符串
     * 要求你让字符串变成左侧全为R，右侧全为G的字符串（可以为0个）
     * 至少需要修改几个字符串
     */
    @Test
    public void ch01() {
        String str = "GGGGG";
        System.out.println(fun2(str));
    }

    /**
     * 思路1：
     * 枚举出左侧的元素从0个到n个。每种情况需要修改多少次，取最少的一种情况。
     * 遍历n个，每个都要从左到右遍历一次查看需要修改多少个。时间复杂度O(N^2)
     */
    public int fun1(String str) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= str.length(); i++) {
            int curr = 0;
            for (int j = 0; j < i; j++) {   //左侧部分要修改的次数
                if (str.charAt(j) != 'R') {
                    curr++;
                }
            }
            for (int j = i; j < str.length(); j++) {    //右侧部分要修改的次数
                if (str.charAt(j) != 'G') {
                    curr++;
                }
            }
            res = Math.min(res, curr);
        }
        return res;
    }

    /**
     * ch01思路2：
     * 我们可以生成两个辅助数组。
     * 分别记录每个位置左侧有几个G，右侧有几个R
     * 这样当我们遍历每个位置时，就可以直接从辅助数组中知道左侧需要修改多少个右侧需要修改多少个。
     */
    public int fun2(String str) {
        int N = str.length();
        int res = Integer.MAX_VALUE;
        int[] Lg = new int[N + 1];
        int[] Rr = new int[N + 1];
        int count = 0;
        for (int i = 1; i <= N; i++) {  // i的左侧有多少个G
            if (str.charAt(i - 1) == 'G') {
                count++;
            }
            Lg[i] = count;
        }
        count = 0;
        for (int i = N - 1; i >= 0; i--) {    //i的右侧有多少个R
            if (str.charAt(i) == 'R') {
                count++;
            }
            Rr[i] = count;
        }
        for (int i = 0; i <= N; i++) {
            int curr = 0;
            curr += Lg[i];
            curr += Rr[i];
            res = Math.min(res, curr);
        }
        return res;
    }

    @Test
    public void compareCh01() {
        int count = 10000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(10);
            StringBuilder str = new StringBuilder();
            while (n-- > 0) {
                str.append(r.nextBoolean() ? "R" : "G");
            }
            int ans = fun1(str.toString());
            int fun = fun2(str.toString());
            if (ans != fun) {
                System.out.println(str);
                System.out.println("预期：" + ans + "\t 实际：" + fun);
            }
        }
    }


    /**
     * ch02:给定一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
     */
    @Test
    public void ch02() {
        int[][] matrix = {
                {1, 1, 0},
                {1, 1, 1},
                {1, 0, 1},
                {1, 1, 1},
        };
        for (int[] arr : matrix) {
            System.out.println(Arrays.toString(arr));
        }
        int fun = ch02Fun2(matrix);
        System.out.println(fun);
        compare02();
    }

    public void compare02() {
        int count = 1000;
        Random r = new Random();
        while (count-- > 0) {
            int[][] matrix = generateRandom01Matrix(r.nextInt(100) + 1, r.nextInt(100) + 1);
            int fun = ch02Fun2(matrix);
            int ans = ch02Fun1(matrix);
            if (ans != fun) {
                Arrays.stream(matrix).forEach(arr -> System.out.println(Arrays.toString(arr)));
                System.out.println("预期：" + ans + "\t 实际：" + fun);
            }
        }
        System.out.println("end");
    }

    /**
     * ch02：暴力枚举思路：遍历每个位置，以每个位置遍历其边长，然后判断边长是否为正方形。
     * 时间复杂度O(N^4)
     */
    public int ch02Fun1(int[][] matrix) {
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {//行
            for (int j = 0; j < matrix[0].length; j++) {//列
                if (matrix[i][j] == 0) continue;
                int len = 1;
                int i2 = i, j2 = j;
                while (i2 < matrix.length && j2 < matrix[0].length) { //遍历边长
                    boolean isSquare = true;
                    for (int k = j + 1; k <= j2; k++) {
                        if (matrix[i][k] != 1) {
                            isSquare = false;
                            break;
                        }
                    }
                    for (int k = i + 1; k <= i2; k++) {
                        if (matrix[k][j] != 1) {
                            isSquare = false;
                            break;
                        }
                    }
                    for (int k = j2; k > j; k--) {
                        if (matrix[i2][k] != 1) {
                            isSquare = false;
                            break;
                        }
                    }
                    for (int k = i2; k > i; k--) {
                        if (matrix[k][j2] != 1) {
                            isSquare = false;
                            break;
                        }
                    }
                    if (isSquare) {
                        len = i2 - i + 1;
                    }
                    i2++;
                    j2++;
                }
                res = Math.max(res, len);
            }
        }
        return res;
    }

    /**
     * ch02：预处理思路：
     * 在暴力枚举中，我们找某位置是否是矩阵，是通过遍历它的四个方向来确定的。O(N)
     * 而我们可以将每个位置右方和下方连续1的个数。使得判断正方形的复杂度变为O(1)
     * 时间复杂度O(N^3)
     */
    public int ch02Fun2(int[][] matrix) {
        int[][] down = getDown(matrix); // 获取矩阵每个位置的下方连续1的个数
        int[][] right = getRight(matrix); // 获取矩阵每个位置的右侧连续1的个数
        int res = 0; // 记录最大的正方形边长
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1) {
                    int len = Math.min(down[i][j], right[i][j]); // 获取当前位置右方和下方连续1的个数中的较小值
                    while (len > 0 && !checkBorder(i, j, len, right, down)) { // 判断是否满足正方形边界条件
                        len--; // 缩小正方形边长
                    }
                    res = Math.max(res, len); // 更新最大的正方形边长
                }
            }
        }
        return res; // 返回最大的正方形边长
    }

    /**
     * 右边界下方和下边界右方1的个数是否能构长度为len的正方形
     *
     * @return
     */
    public boolean checkBorder(int i, int j, int len, int[][] right, int[][] down) {
        return down[i][j + len - 1] >= len && right[i + len - 1][j] >= len; //因为len包括了自己。所以需要len-1
    }

    /**
     * 返回每个位置右侧有多少个1
     */
    public int[][] getRight(int[][] matrix) {
        int[][] res = new int[matrix.length][matrix[0].length];
        for (int i = 0; i != matrix.length; i++) {
            for (int j = matrix[0].length - 1; j >= 0; j--) {
                if (matrix[i][j] == 1) {
                    if (j == matrix[0].length - 1) {
                        res[i][j] = 1;
                        continue;
                    }
                    res[i][j] = res[i][j + 1] + 1;
                }
            }
        }
        return res;
    }

    public int[][] getDown(int[][] matrix) {
        int[][] res = new int[matrix.length][matrix[0].length];
        for (int i = matrix.length - 1; i >= 0; i--) {
            for (int j = 0; j != matrix[0].length; j++) {
                if (matrix[i][j] == 1) {
                    if (i == matrix.length - 1) {
                        res[i][j] = 1;
                        continue;
                    }
                    res[i][j] = res[i + 1][j] + 1;
                }
            }
        }
        return res;
    }

    public int[][] generateRandom01Matrix(int rowSize, int colSize) {
        int[][] res = new int[rowSize][colSize];
        for (int i = 0; i != rowSize; i++) {
            for (int j = 0; j != colSize; j++) {
                res[i][j] = (int) (Math.random() * 2);
            }
        }
        return res;
    }
}
